using System;
using System.Collections.Generic;
using System.Text;

namespace COME342.CollisionResolution.BinaryTree
{

    public abstract class BinaryTreeADT<T>
    {
        /*public abstract BinaryTreeADT<T> Left { get; }
        public abstract BinaryTreeADT<T> Right { get; }
        public abstract BinaryTreeADT<T> Parent { get; }*/

        public T data;

        public BinaryTreeADT()
        {
        }
        
        public BinaryTreeADT(T data)
        {
            this.data = data;
        }

        public abstract bool IsRoot();        
        public abstract bool IsLeaf();
        public abstract bool IsLeftEmpty();
        public abstract bool IsRightEmpty();

        public abstract List<T> PreOrderTraverse();
        public abstract List<T> InOrderTraverse();
        public abstract List<T> PostOrderTraverse();

        /*public abstract void AddToLeft(T data);
        public abstract void AddToRight(T data);*/
        public abstract override string ToString();
    }

    public class BinaryTree<T>  : BinaryTreeADT<T>     
    {
        public BinaryTree<T> left = null;
        public BinaryTree<T> right = null;
        public BinaryTree<T> parent = null;        

        public BinaryTree(T data)
        {
            this.data = data;
        }

        public BinaryTree()
        {
        }

        public override bool IsRoot()
        {
            return parent == null;
        }

        public BinaryTree<T> GetRoot()
        {
            BinaryTree<T> bt;
            bt = this;
            while (!bt.IsRoot())
                bt = bt.parent;
            return bt;
        }

        public override bool IsLeaf()
        {
            return left == null && right == null;
        }

        public override bool IsLeftEmpty()
        {
            return left == null;
        }

        public override bool IsRightEmpty()
        {
            return right == null;
        }

        private void PreOrderTraverse(ref List<T> ret)
        {
            ret.Add(data);
            if (left != null)
                left.PreOrderTraverse(ref ret);
            if (right != null)
                right.PreOrderTraverse(ref ret);
        }

        public override List<T> PreOrderTraverse()
        {
            List<T> ret = new List<T>();
            PreOrderTraverse(ref ret);
            return ret;
        }

        public override List<T> InOrderTraverse()
        {
            List<T> ret = new List<T>();
            InOrderTraverse(ref ret);
            return ret;
        }

        private void InOrderTraverse(ref List<T> ret)
        {
            if (left != null)
                left.InOrderTraverse(ref ret);
            ret.Add(data);
            if (right != null)
                right.InOrderTraverse(ref ret);
        }

        public override List<T> PostOrderTraverse()
        {
            List<T> ret = new List<T>();
            PostOrderTraverse(ref ret);
            return ret;
        }

        private void PostOrderTraverse(ref List<T> ret)
        {
            if (left != null)
                left.PostOrderTraverse(ref ret);            
            if (right != null)
                right.PostOrderTraverse(ref ret);
            ret.Add(data);
        }

        private void AddToLeft(T data)
        {
            if (left != null)
                throw new ArgumentException("Left subtree is not null. Can not insert.");
            left = new BinaryTree<T>(data);
            left.parent = this;
        }

        private void AddToRight(T data)
        {
            if (right != null)
                throw new ArgumentException("Right subtree is not null. Can not insert.");
            right = new BinaryTree<T>(data);
            right.parent = this;
        }

        public void RemoveLeftLeaf()
        {
            if (left == null)
                throw new ArgumentException("Left subtree is null. Can not remove it.");
            if (!left.IsLeaf())
                throw new ArgumentException("Left subtree is not a leaf. Can not remove it with this method.");
            left = null;
        }

        public void RemoveRightLeaf()
        {
            if (right == null)
                throw new ArgumentException("Right subtree is null. Can not remove it.");
            if (!right.IsLeaf())
                throw new ArgumentException("Right subtree is not a leaf. Can not remove it with this method.");
            right = null;
        }

        public void RemoveLeftSubtree()
        {
            left = null;
        }

        public void RemoveRightSubtree()
        {
            right = null;
        }

        public override string ToString()
        {
            return data.ToString() + " L:" + (left == null ? "-" : left.data.ToString()) + " R:" + (right == null ? "-" : right.data.ToString());
        }

    }

    public class BinarySearchTree<T> : BinaryTreeADT<T> where T : IComparable
    {
        public BinarySearchTree<T> left = null;
        public BinarySearchTree<T> right = null;
        public BinarySearchTree<T> parent = null;

        public BinarySearchTree(T data)
        {
            this.data = data;
        }

        public void Insert(T data)
        {
            if (this.data == null)
            {
                this.data = data;
                return;
            }

            if (this.data.CompareTo(data) > 0)
            {
                if (this.left != null)
                    this.left.Insert(data);
                else
                    this.left = new BinarySearchTree<T>(data);                
            }
            else if (this.data.CompareTo(data) < 0)
            {
                if (this.right != null)
                    this.right.Insert(data);
                else
                    this.right = new BinarySearchTree<T>(data);
            }
        }

        public override bool IsRoot()
        {
            return parent == null;
        }

        public override bool IsLeaf()
        {
            return left == null && right == null;
        }

        public override bool IsLeftEmpty()
        {
            return left == null;
        }

        public override bool IsRightEmpty()
        {
            return right == null;
        }

        private void PreorderTraverse(ref List<T> ret)
        {
            ret.Add(data);
            if (left != null)
                left.PreorderTraverse(ref ret);
            if (right != null)
                right.PreorderTraverse(ref ret);
        }

        public override List<T> PreOrderTraverse()
        {
            List<T> ret = new List<T>();
            PreorderTraverse(ref ret);
            return ret;
        }

        public override List<T> InOrderTraverse()
        {
            List<T> ret = new List<T>();
            InOrderTraverse(ref ret);
            return ret;
        }

        private void InOrderTraverse(ref List<T> ret)
        {
            if (left != null)
                left.InOrderTraverse(ref ret);
            ret.Add(data);
            if (right != null)
                right.InOrderTraverse(ref ret);
        }

        public override List<T> PostOrderTraverse()
        {
            List<T> ret = new List<T>();
            PostOrderTraverse(ref ret);
            return ret;
        }

        private void PostOrderTraverse(ref List<T> ret)
        {
            if (left != null)
                left.PostOrderTraverse(ref ret);
            if (right != null)
                right.PostOrderTraverse(ref ret);
            ret.Add(data);
        }

        public void AddToLeft(T data)
        {
            if (left != null)
                throw new ArgumentException("Left subtree is not null. Can not insert.");
            left = new BinarySearchTree<T>(data);
            left.parent = this;
        }

        public void AddToRight(T data)
        {
            if (right != null)
                throw new ArgumentException("Right subtree is not null. Can not insert.");
            right = new BinarySearchTree<T>(data);
            right.parent = this;
        }

        public override string ToString()
        {
            return data.ToString() + " L:" + (left == null ? "-" : left.data.ToString()) + " R:" + (right == null ? "-" : right.data.ToString());
        }        
    }
}
